This invention generally relates to the field of queuing systems, and more particularly to the determination of worst case latency (WCL).
In a queuing system there are typically a number of channels which can access system resources. As the system resources are shared, only one channel at a time can be granted access. If there are multiple contending access requests of different channels, a pre-defined schematics is employed in prior art queuing systems to select one of the requesting channels for granting of the system resources. After grant the selected requesting channel is the master of the system resources during a certain time slot which can be of fixed or variable length. After the time slot another requesting channel is selected from the waiting queue for grant according to the schematics. Such a schematics typically is implemented in an bus arbiter or scheduler.
Such queuing systems can be found in multi processor systems where a plurality of processors is coupled to the same bus which can only service one processor at a time. Another field of application is in the field of micro controllers. A micro controller has a number of input/output channels which can access the common system resources of the micro controller to perform different kinds of calculations and transformations according to the needs of the technical environment. Micro controllers are used in a wide field of applications, for example in automobile electronics, control electronics of household appliances, control systems of chemical factories as well as in mobile telephone systems.
In such applications the channels connected to the micro controller serve to interact with the real world technical environment. To comply with the needs of the technical environment each channel has to have a minimum band width to ensure proper operation of the technical system. In such a system it is highly desirable to guarantee a minimum channel band width also under worst case operating conditions to prevent failure.
To facilitate the design of a queuing system a method for determining the worst case latency (WCL) has to be employed. The more accurate such a method is, the more effective the common system resources of the resulting queuing system can be used by the requesting channels. From the xe2x80x9cModular micro controller family TPU Time processor Unitxe2x80x9d, Reference Manual, published by Motorola, Inc., especially appendix C a method of estimating worst-case service latency in a queuing system relying on a scheduler which applies a priority scheme with priority passing rules is known. No method has been available to exactly determine the worst-case latency with mathematical exactness and without having to add security margins.
It is therefore an object of the invention to provide an improved method for determining a number of accesses granted to requesting channels in a queuing system as well as an improved computer program for carrying out such a method and an apparatus being designed accordingly.
This and other problems are solved by the invention basically by applying the features laid down in the independent claims. Preferred embodiments are given in the dependent claims.
The inventions allows to determine a number of access granted to requesting channels during WCL of a selected channel of the system. This number of access can be used for different purposes during the system design. In particular, the duration of the WCL itself can be determined based on this number of access according to the invention.
The invention is particularly advantageous in that it allows to carry out the calculation of the worst case service latency automatically by means of a computer. This allows to investigate a large number of different timing scenarios in order to optimize the queuing system for the particular needs of the technical environment.
Further the method of the invention yields accurate results so that it is not necessary to add security margins in the system to guarantee minimal band width for all channels. As a consequence an apparatus which is designed accordingly features improved utilization of the system resources and thereby allows more accurate control or faster operating speed of the overall technical system according to it""s field of use.
FIG. 1 shows a schematic block diagram of an apparatus which has a queuing system in accordance with the principles of the invention;
FIG. 2 shows an ordered list of priorities which is used in the scheduler of the apparatus of FIG. 1;
FIG. 3 shows two sequences of time slots to determine a worst time slot for an access request;
FIG. 4-FIG. 8 show sequences of time slots and the associated number of time slots during WCL;
FIG. 9 shows a table which lists the amounts of slots in WCL for different amounts of active high priority channels for the case of high and middle priority requesting channels;
FIG. 10 shows a flow chart of one embodiment of the method for determining a number of accesses granted during WCL;
FIG. 11 shows a mathematical model as an alternative to carrying out the method of FIG. 10;
FIG. 12 shows mathematical model similar to the mathematical model of FIG. 11 to model the information contained in the table of FIG. 13;
FIG. 13 shows a table similar to the table of FIG. 9 for the case that all priorities are present;
FIG. 14 shows a table similar to the table of FIG. 13 for the case of the WCL of the middle-priority channel as well as the associated mathematical model;
FIG. 15 shows a table similar to the table of FIG. 14 for the case of the WCL of the low-priority channel as well as the associated mathematical model;
FIG. 16 shows the assignment of channels to functions and their corresponding priorities;
FIG. 17 shows two examples of function state flow charts;
FIG. 18 shows the calculation of the WCL based on state execution times of the functions; and
FIG. 19 is a flow chart illustrating one embodiment of the invention to determine the WCL.